/**
 * Created With IntelliJ IDEA
 * Description:PTA：根据后序和中序遍历输出先序遍历
 * User: DELL
 * Data: 2022-12-23
 * Time: 23:06
 */


/**
 * 本题要求根据给定的一棵二叉树的后序遍历和中序遍历结果，输出该树的先序遍历结果。
 * 输入格式:
 * 第一行给出正整数N(≤30)，是树中结点的个数。随后两行，每行给出N个整数，分别对应后序遍历和中序遍历结果，数字间以空格分隔。题目保证输入正确对应一棵二叉树。
 * 输出格式:
 * 在一行中输出Preorder: 以及该树的先序遍历结果。数字间有1个空格，行末不得有多余空格。
 * 输入样例:
 * 7
 * 2 3 1 5 7 6 4
 * 1 2 3 4 5 6 7
 * 输出样例:
 * Preorder: 4 1 3 2 6 5 7
 */
import java.util.Scanner;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

public class Main {
    static int[] postArr;//后序遍历数组
    static int[] midArr;//中序遍历数组

    public static void main(String[] args) {

        Scanner scan = new Scanner(System.in);

        int n = scan.nextInt();

        postArr = new int[n+1];
        midArr = new int[n+1];
        //后序遍历
        for (int i = 1; i <= n; i++) {
            postArr[i] = scan.nextInt();
        }
        //中序遍历
        for (int i = 1; i <= n; i++) {
            midArr[i] = scan.nextInt();
        }
        //根据后序遍历和中序遍历重构一棵树
        TreeNode root = restore(1,n,1,n);
        //先序遍历输出打印
        System.out.print("Preorder:");
        preorder(root);
    }

    /**
     *
     * @param postStart  后续遍历数组的下标
     * @param postEnd
     * @param midStart   中序遍历数组的下标
     * @param midEnd
     * @return
     */
    private static TreeNode restore(int postStart,int postEnd,int midStart,int midEnd) {
        //判空处理
        if (postStart > postEnd || midStart > midEnd) {
            return null;
        }
        //先找出根节点
        TreeNode root = new TreeNode();
        root.val = postArr[postEnd];
        //再找出根节点的左右结点
        for (int i = midStart; i <= midEnd; i++) {
            if (midArr[i] == root.val) {
                root.left = restore(postStart,postEnd-(midEnd-i)-1,midStart,i-1);
                root.right = restore(postEnd-(midEnd-i),postEnd-1,i+1,midEnd);
                return root;
            }
        }
        return root;
    }
    private static void preorder(TreeNode root) {
        if (root != null) {
            System.out.print(" " + root.val);
            preorder(root.left);
            preorder(root.right);
        }
    }
}